2.2 链表

链表是一种常见的线性数据结构，与数组不同的是，链表中的元素并不存储在连续的内存空间中，而是通过指针连接在一起。

链表非常适合需要频繁插入、删除操作的场景，因为它不需要像数组那样频繁移动数据。

本节代码存放目录为 lesson3

概念及原理

单向链表

单向链表是一种由多个节点组成的线性数据结构。每个节点包含两个部分：

• 数据部分：存储节点中的实际数据。

• 指针部分：存储指向下一个节点的地址。

链表中的节点通过指针彼此连接，最后一个节点指向 nil，表示链表的结束。

单向链表的结构示意图如下所示：

+-------+    +-------+    +-------+    +-------+
|  1    | -> |  2    | -> |  3    | -> |  4    | -> nil
+-------+    +-------+    +-------+    +-------+

从上面的示意图中我们可以看出，单向链表与数组其实有一些相似之处。

• 数组是线性结构，所有元素存储在连续的内存空间中，每个元素只包含一个值，因此我们可以通过索引快速访问任意位置的元素，时间复杂度为 O(1)。

• 单向链表也是线性结构，但它的元素（节点）在内存中不连续存储。每个节点除了存储数据外，还包含一个指向下一个节点的指针。查询某个节点时，我们需要从头节点开始，逐个访问每个节点，直到找到目标元素，时间复杂度为 O(n)。

单向链表的优缺点如下：

• 优点：插入和删除操作效率高，特别是在链表的头部或中部。

• 缺点：无法通过索引直接访问元素，需要从头开始遍历链表才能找到目标元素。

单向链表的操作如下：

• 插入节点：在链表的头部或尾部插入节点，或者在中间插入节点。

• 删除节点：根据值或位置删除节点。

• 遍历链表：只能从头节点开始，逐个访问链表中的每个节点。

双向链表

双向链表是一种与单向链表类似的链表结构，但它的每个节点都有两个指针：

• 前驱指针：指向前一个节点。

• 后继指针：指向后一个节点。

双向链表可以从任意节点向前或向后遍历，操作更加灵活。

双向链表的结构示意图如下：

nil <- +-------+ <-> +-------+ <-> +-------+ <-> +-------+ -> nil
       |  1    |     |  2    |     |  3    |     |  4    |
       +-------+     +-------+     +-------+     +-------+

从上面的示意图我们可以看出，双向链表与单向链表最大的区别就是：双向不仅指向前一个元素，还指向后一个元素。

也就是说双向链表可以从后往前查找，也可以从前往后查找，而单向链表则只能从先往后去查找数据。

双向链表的优缺点如下：

• 优点：可以向前或向后遍历链表，插入、删除节点更加灵活。

• 缺点：相比单向链表，双向链表需要更多的内存来存储两个指针。

双向链表的操作如下：

• 插入节点：可以在链表的任何位置插入节点，前后指针都需要更新。

• 删除节点：根据值或位置删除节点，同时更新前驱和后继指针。

• 遍历链表：可以从任意节点向前或向后遍历链表。

循环链表

循环链表是一种特殊的链表结构，它的最后一个节点的指针指向链表的头节点，形成一个环，而不是指向 nil。

循环链表可以是单向的，也可以是双向的。

循环链表的结构示意图如下：

• 单向循环链表：

+-------+    +-------+    +-------+    +-------+
|  1    | -> |  2    | -> |  3    | -> |  4    | -> (回到 1)
+-------+    +-------+    +-------+    +-------+
     ^                                            |
     |--------------------------------------------|


完整结构：

+-------+       +-------+
|   1   | ----> |   2   |
+-------+       +-------+
   ^               |
   |               v
+-------+       +-------+
|   4   | <---- |   3   |
+-------+       +-------+

从示意图我们可以看出，单向循环链表与单向链表最大的区别就是：单向循环链表的最后一个元素还会指向第一个元素。

• 双向循环链表：

+-------+ <-> +-------+ <-> +-------+ <-> +-------+
|  1    |     |  2    |     |  3    |     |  4    |
+-------+     +-------+     +-------+     +-------+
    ^                                          ^
    |------------------------------------------|


完整结构：

+-------+       +-------+
|   1   | <-->  |   2   |
+-------+       +-------+
   ^               ^
   |               |
   v               v
+-------+       +-------+
|   4   | <-->  |   3   |
+-------+       +-------+

从示意图我们可以看出，双向循环链表与单向链表最大的却别就是：双向循环链表的最后一个元素还会与第一个元素互相指向。

总的来说循环链表就像是我们自行车的链条一样的，通过每一个扣的连接，最终形成了一个循环的圈套。

循环链表的优缺点如下：

• 优点：循环链表适合处理循环数据流的问题，头尾相连，能够遍历链表的每个节点而无需担心终点。

• 缺点：在处理过程中不容易判断链表结束，必须小心避免死循环。

循环链表的操作如下：

• 插入节点：可以在头部或尾部插入节点，尾部节点的指针需要重新指向头节点。

• 删除节点：根据值或位置删除节点，更新前驱和后继节点的指针。

• 遍历链表：从任意节点开始遍历，循环遍历链表中的所有节点。

Go语言的实现

单向链表的实现

// Node 定义单向列表的节点结构
type Node struct {
    // 数据
    data int
    // 指向下一个节点
    next *Node
}

func appendNode(head *Node, data int) *Node {
    newNode := &Node{
        data: data,
    }

    // 第一个元素
    if head == nil {
        return newNode
    }

    current := head

    // 如果当前元素是有指向的，那么使用下一个
    for current.next != nil {
        current = head.next
    }

    // 指向新的元素
    current.next = newNode

    return head
}

func deleteNode(head *Node, data int) *Node {
    if head == nil {
        return nil
    }

    current := head
    for current.next != nil {
        if current.next.data == data {
            current.next = current.next.next
            break
        }
        current = current.next
    }

    return head
}

func printNode(head *Node) {
    current := head

    // 读取所有元素展示
    for current != nil {
        fmt.Print(current.data, " -> ")
        current = current.next
    }
    fmt.Println("nil")
}

func main() {
    var (
        head *Node
    )
    head = appendNode(head, 1)
    head = appendNode(head, 2)
    head = appendNode(head, 3)
    printNode(head)

    head = deleteNode(head, 2)
    printNode(head)
}

执行输入如下所示：

1 -> 2 -> 3 -> nil
1 -> 3 -> nil

在上面的代码中，我们使用Go语言实现了单向链表，其实只需要理解了它的本质，那么使用起来就会比较简单。

我们只需要关注一点，就是每一个元素都有一个指针指向，那么最终形成的就是一条铁链，一个链着下一个。

双向链表的实现

// Node 定义双向列表的节点结构
type Node struct {
    // 数据
    data int
    // 指向上一个节点
    prev *Node
    // 指向下一个节点
    next *Node
}

func appendNode(head *Node, data int) *Node {
    newNode := &Node{
        data: data,
    }
    if head == nil {
        return newNode
    }

    current := head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
    newNode.prev = current
    return head
}

func delNode(head *Node, data int) *Node {
    if head == nil {
        return nil
    }

    current := head
    for current.next != nil {
        // 匹配到
        if current.next.data == data {
            // 更新当前的后续指向
            current.next = current.next.next
            if current.next.next != nil {
                // 更新新的前序指向，将它们链接起来
                current.next.next.prev = current
            }
            break
        }
        current = current.next
    }
    return head
}

func printNode(head *Node) {
    current := head
    for current != nil {
        fmt.Printf("%d <-> ", current.data)
        current = current.next
    }
    fmt.Println("nil")
}

func main() {
    var (
        head *Node
    )
    head = appendNode(head, 1)
    head = appendNode(head, 2)
    head = appendNode(head, 3)
    printNode(head)

    delNode(head, 2)
    printNode(head)
}

结果输出如下所示：

1 <-> 2 <-> 3 <-> nil
1 <-> 3 <-> nil

双向链表的实现其实与单向是差不多的，只不过在结构体中多了prev，也就是说我们在添加元素时需要将元素的前序指向也进行标记。

所以我们其实可以从前往后找，同时我们也可以通过遍历从后往前找，只需要知道其中的任意一个元素，都可以找到前面、后面的所有元素。

循环链表的实现

// Node 定义单向循环链表节点结构
type Node struct {
    data int
    // 指向下一个元素的指针节点
    Next *Node
}

func appendNode(head *Node, data int) *Node {
    newNode := &Node{
        data: data,
    }
    if head == nil {
        newNode.Next = newNode
        return newNode
    }

    current := head
    for current.Next != head {
        current = current.Next
    }
    current.Next = newNode
    newNode.Next = head

    return head
}

func delNode(head *Node, data int) *Node {
    if head == nil {
        return nil
    }

    current := head
    for current.Next != head {
        if current.Next.data == data {
            current.Next = current.Next.Next
            break
        }
        current = current.Next
    }
    return head
}

func printNode(head *Node) {
    if head == nil {
        return
    }

    current := head
    for current.Next != nil {
        fmt.Printf("%d -> ", current.data)

        current = current.Next
        if current == head {
            // 循环到了开头
            break
        }
    }
    fmt.Println("(回到头节点)")
}

func main() {
    var (
        head *Node
    )
    head = appendNode(head, 1)
    head = appendNode(head, 2)
    head = appendNode(head, 3)
    printNode(head)

    head = delNode(head, 2)
    printNode(head)
}

结果输出如下所示：

1 -> 2 -> 3 -> (回到头节点)
1 -> 3 -> (回到头节点)

循环链表的实现与原本的单向、双向其实是差不多的。只需要将原本末尾节点再次链接指向到头部节点即可。

在循环链表中需要注意出现死循环，在更新节点或者增删节点时是比较容易出现这个问题的。

总的来说，链表的实现其实就是通过结构体字段指针进行指向，形成一个铁链结构。